package main.java.day04;

import java.util.*;

/**
 * 给定一个只包括
 * <p>
 * <p>
 * '('，')'，'{'，'}'，'['，']' 
 * <p>
 * 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "()"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "()[]{}"
 * 输出: true
 * 示例 3:
 * <p>
 * 输入: "(]"
 * 输出: false
 * 示例 4:
 * <p>
 * 输入: "([)]"
 * 输出: false
 * 示例 5:
 * <p>
 * 输入: "{[]}"
 * 输出: true
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day04 {

    static class Solution {
        public static boolean isValid(String s) {
            if(s==null || "".equals(s)) {
                return true;
            }
            //用栈保存 (，[，{
            Stack<Character> stack = new Stack<Character>();
            //map中保存的是 ):(, ]:[,}:{
            //当遍历到 )时候就会去map中找对应的value，也就是(
            //再用这个value和stack弹出的元素比较，如果相等则匹配上，不等则返回false
            //这里也可以用数组来存，我为了简单就用map表示了
            HashMap<Character,Character> map = new HashMap<Character,Character>();
            map.put(')','(');
            map.put(']','[');
            map.put('}','{');
            for(int i=0;i<s.length();i++) {
                char c = s.charAt(i);
                //如果map中不包含 (,[,{，就将这个字符放入栈中
                if(!map.containsKey(c)) {
                    stack.add(c);
                } else {
                    //如果遍历的字符不再map中，也就是说这个字符是),],}，那么就要跟栈中的元素比较
                    //首先要判断栈是否为空，如果输入的字符是 )() ，那么当遍历到第一个)时，栈为空
                    if(stack.size()==0) {
                        return false;
                    }
                    //取出栈顶的元素
                    Character tmp = stack.pop();
                    //假设当前遍历到的元素是 ]，那么从map中取到的value就是 [
                    //如果栈顶的元素是 (，则不匹配返回false，否则继续
                    if(map.get(c)!=tmp) {
                        return false;
                    }
                }
            }
            //返回的时候还要判断栈是否为空
            //如果输入的字符串是 (((，那么最后栈就不为空
            return (stack.empty()? true : false);

        }

        /**
         * 解法2
         * @param s
         * @return
         */
        public static boolean isValid2(String s) {
            if (s.length() == 0)
                return true;
            if ((s.length() & 1) == 1)
                return false;
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                switch (s.charAt(i)) {
                    case '(':
                    case '[':
                    case '{':
                        stack.push(s.charAt(i));
                        continue;
                    case ')':
                        if (stack.isEmpty() || stack.pop() != '(')
                            return false;
                        continue;
                    case ']':
                        if (stack.isEmpty() || stack.pop() != '[')
                            return false;
                        continue;
                    case '}':
                        if (stack.isEmpty() || stack.pop() != '{')
                            return false;
                        continue;
                }
            }
            return stack.isEmpty();
        }
    }

    public static void main(String[] args) {
        System.out.println(Solution.isValid("()"));
    }
}
